package me.mingshan.leetcode;

import java.math.BigDecimal;

/**
 * https://leetcode.cn/problems/split-linked-list-in-parts/
 * <p>
 * 725.分隔链表
 * <p>
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 * <p>
 * 每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 * <p>
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 * <p>
 * 返回一个由上述 k 部分组成的数组。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = [1,2,3], k = 5
 * 输出：[[1],[2],[3],[],[]]
 * 解释：
 * 第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
 * 最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。
 * 示例 2：
 * <p>
 * <p>
 * 输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
 * 输出：[[1,2,3,4],[5,6,7],[8,9,10]]
 * 解释：
 * 输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。
 *
 * @author hanjuntao
 * @date 2025/7/28 0028
 */
public class L_725_split_linked_list_in_parts {

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);

        ListNode[] result = splitListToParts(node, 5);
        for (ListNode node1 : result) {
            if (node1 == null) {
                System.out.println("null");
            } else {
                ListNode.print(node1);
            }
        }

        System.out.println("------------------------");

        // 1,2,3,4,5,6,7,8,9,10
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(3);
        node1.next.next.next = new ListNode(4);
        node1.next.next.next.next = new ListNode(5);
        node1.next.next.next.next.next = new ListNode(6);
        node1.next.next.next.next.next.next = new ListNode(7);
        node1.next.next.next.next.next.next.next = new ListNode(8);
        node1.next.next.next.next.next.next.next.next = new ListNode(9);
        node1.next.next.next.next.next.next.next.next.next = new ListNode(10);
        ListNode[] result1 = splitListToParts(node1, 3);
        for (ListNode node2 : result1) {
            if (node2 == null) {
                System.out.println("null");
            } else {
                ListNode.print(node2);
            }
        }

    }

    /**
     * 思路：
     * 1. 获取链表长度
     * 2. 确定每一部分长度
     * 3. 创建结果数组result，长度为 k
     * 4. 循环result数组，将原链表数据复制到结果数组中，当一个链表处理完，需要断开链表
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode[] splitListToParts(ListNode head, int k) {
        // 获取链表长度
        int length = 0;

        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        BigDecimal lenB = new BigDecimal(length);
        BigDecimal kB = new BigDecimal(k);

        BigDecimal[] bigDecimals = lenB.divideAndRemainder(kB);
        // 正数
        int quotient = bigDecimals[0].intValue();
        // 余数
        int remainder = bigDecimals[1].intValue();

        // 确定每一部分的长度
        int[] lenList = new int[k];

        for (int i = 0; i < k; i++) {
            // 如果只有余数
            if (quotient == 0 && remainder > 0) {
                lenList[i] = 1;
                remainder--;
            } else if (quotient > 0) {
                int len = quotient;

                // 剩余数
                if (remainder > 0) {
                    len++;
                    remainder--;
                }
                lenList[i] = len;
            }
        }

        // 分为k组
        ListNode[] result = new ListNode[k];

        curr = head;

        for (int i = 0; i < k; i++) {
            ListNode listNode = result[i];
            Integer len = lenList[i];

            while (len > 0) {
                if (listNode == null) {
                    listNode = curr;
                    result[i] = listNode;
                } else {
                    listNode.next = curr;
                    listNode = listNode.next;
                }

                len--;
                curr = curr.next;
            }

            if (listNode != null) {
                // 需要切断链表
                listNode.next = null;
            }
        }

        return result;
    }

}
